mod Pでの組み合わせ
組み合わせ(
二項係数
)
$ _nC_k = C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}
を大きな数n, kについて求めたいとする。
mod Pでの値で良いとする
それが求まれば複数の値から
中国剰余定理
で元の値が復元できるから
剰余を取った後で普通の割り算を行うことはできない。
そこで
mod Pでの逆元
を計算して掛ける。
単発での計算なら対数オーダーで逆元を作成
大量に計算するなら
逆元テーブル
を作れば一つ当たりは定数オーダーになる
剰余群逆元漸化式の導出
二項係数テーブル
巨大なnについての二項係数